// ***** This file is automatically generated from MathMDE.java.jpp

package daikon.util;
import java.util.*;

/** Mathematical utilities. */
public final class MathMDE {
  private MathMDE() { throw new Error("do not instantiate"); }

  ///
  /// Function versions of Java operators
  ///

  public static int negate(int a) {
    return -a;
  }

  public static long negate(long a) {
    return -a;
  }

  public static double negate(double a) {
    return -a;
  }

  public static int bitwiseComplement(int a) {
    return ~a;
  }

  public static long bitwiseComplement(long a) {
    return ~a;
  }

  public static int mul(int x, int y) {
    return x * y;
  }

  public static long mul(long x, long y) {
    return x * y;
  }

  public static double mul(double x, double y) {
    return x * y;
  }

  public static int div(int x, int y) {
    return x / y;
  }

  public static long div(long x, long y) {
    return x / y;
  }

  public static double div(double x, double y) {
    return x / y;
  }

  public static int mod(int x, int y) {
    return x % y;
  }

  public static long mod(long x, long y) {
    return x % y;
  }

  public static int lshift(int x, int y) {
    return x << y;
  }

  public static long lshift(long x, long y) {
    return x << y;
  }

  public static int rshiftSigned(int x, int y) {
    return x >> y;
  }

  public static long rshiftSigned(long x , long y) {
    return x >> y;
  }

  public static int rshiftUnsigned(int x, int y) {
    return x >>> y;
  }

  public static long rshiftUnsigned(long x, long y) {
    return x >>> y;
  }

  public static int bitwiseAnd(int x, int y) {
    return x & y;
  }

  public static long bitwiseAnd(long x, long y) {
    return x & y;
  }

  public static int logicalAnd(int x, int y) {
    return ((x!=0) && (y!=0)) ? 1 : 0;
  }

  public static long logicalAnd(long x, long y) {
    return ((x!=0) && (y!=0)) ? 1 : 0;
  }

  public static int bitwiseXor(int x, int y) {
    return x ^ y;
  }

  public static long bitwiseXor(long x, long y) {
    return x ^ y;
  }

  public static int logicalXor(int x, int y) {
    return ((x!=0) ^ (y!=0)) ? 1 : 0;
  }

  public static long logicalXor(long x, long y) {
    return ((x!=0) ^ (y!=0)) ? 1 : 0;
  }

  public static int bitwiseOr(int x, int y) {
    return x | y;
  }

  public static long bitwiseOr(long x, long y) {
    return x | y;
  }

  public static int logicalOr(int x, int y) {
    return ((x!=0) || (y!=0)) ? 1 : 0;
  }

  public static long logicalOr(long x, long y) {
    return ((x!=0) || (y!=0)) ? 1 : 0;
  }

  ///
  /// negation
  ///

  public static int sign(int a) {
    if (a==0)
      return 0;
    else if (a>0)
      return 1;
    else
      return -1;
  }

  ///
  /// exponentiation
  ///

  /**
   * Returns of value of the first argument raised to the
   * power of the second argument.
   * @see Math#pow(double, double)
   **/
  public static int pow(int base, int expt) throws ArithmeticException {
    return pow_fast(base, expt);
  }

  public static long pow(long base, long expt) throws ArithmeticException {
    return pow_fast(base, expt);
  }

  public static int pow_fast(int base, int expt) throws ArithmeticException {
    if (expt < 0)
      throw new ArithmeticException("Negative exponent passed to pow");

    int this_square_pow = base;
    int result = 1;
    while (expt>0) {
      if ((expt & 1) != 0)
        result *= this_square_pow;
      expt >>= 1;
      this_square_pow *= this_square_pow;
    }
    return result;
  }

  public static long pow_fast(long base, long expt) throws ArithmeticException {
    if (expt < 0)
      throw new ArithmeticException("Negative exponent passed to pow");

    long this_square_pow = base;
    long result = 1;
    while (expt>0) {
      if ((expt & 1) != 0)
        result *= this_square_pow;
      expt >>= 1;
      this_square_pow *= this_square_pow;
    }
    return result;
  }

  public static int pow_slow(int base, int expt) throws ArithmeticException {
    if (expt < 0)
      throw new ArithmeticException("Negative exponent passed to pow");

    int result = 1;
    for (int i=0; i<expt; i++)
      result *= base;
    return result;
  }

  ///
  /// gcd
  ///

  /** Return the greatest common divisor of the two arguments. */
  public static int gcd(int a, int b) {

    // Euclid's method
    if (b == 0)
      return (Math.abs(a));
    a = Math.abs(a);
    b = Math.abs(b);
    while (b != 0) {
      int tmp = b;
      b = a % b;
      a = tmp;
    }
    return a;
  }

  /** Return the greatest common divisor of the elements of int array a. */
  public static int gcd(int[] a) {
    // Euclid's method
    if (a.length == 0) {
      return 0;
    }
    int result = a[0];
    for (int i=1; i<a.length; i++) {
      result = gcd(a[i], result);
      if ((result == 1) || (result == 0))
        return result;
    }
    return result;
  }

  /**
   * Return the gcd (greatest common divisor) of the differences
   * between the elements of int array a.
   **/
  public static int gcd_differences(int[] a) {
    // Euclid's method
    if (a.length < 2) {
      return 0;
    }
    int result = a[1] - a[0];
    for (int i=2; i<a.length; i++) {
      result = gcd(a[i] - a[i-1], result);
      if ((result == 1) || (result == 0))
        return result;
    }
    return result;
  }

  /// gcd -- version for manipulating long (rather than int) values

  /** Return the greatest common divisor of the two arguments. */
  public static long gcd(long a, long b) {

    // Euclid's method
    if (b == 0)
      return (Math.abs(a));
    a = Math.abs(a);
    b = Math.abs(b);
    while (b != 0) {
      long tmp = b;
      b = a % b;
      a = tmp;
    }
    return a;
  }

  /** Return the greatest common divisor of the elements of long array a. */
  public static long gcd(long[] a) {
    // Euclid's method
    if (a.length == 0) {
      return 0;
    }
    long result = a[0];
    for (int i=1; i<a.length; i++) {
      result = gcd(a[i], result);
      if ((result == 1) || (result == 0))
        return result;
    }
    return result;
  }

  /**
   * Return the gcd (greatest common divisor) of the differences
   * between the elements of long array a.
   **/
  public static long gcd_differences(long[] a) {
    // Euclid's method
    if (a.length < 2) {
      return 0;
    }
    long result = a[1] - a[0];
    for (int i=2; i<a.length; i++) {
      result = gcd(a[i] - a[i-1], result);
      if ((result == 1) || (result == 0))
        return result;
    }
    return result;
  }

  /** Return the greatest common divisor of the two arguments. */
  public static double gcd(double a, double b) {

    if (a == Double.POSITIVE_INFINITY
        || a == Double.NEGATIVE_INFINITY
        || Double.isNaN(a)
        || b == Double.POSITIVE_INFINITY
        || b == Double.NEGATIVE_INFINITY
        || Double.isNaN(b)) {
      return Double.NaN;
    }

    // Euclid's method
    if (b == 0)
      return (Math.abs(a));
    a = Math.abs(a);
    b = Math.abs(b);
    while (b != 0) {
      double tmp = b;
      b = a % b;
      a = tmp;
    }
    return a;
  }

  /** Return the greatest common divisor of the elements of double array a. */
  public static double gcd(double[] a) {
    // Euclid's method
    if (a.length == 0) {
      return 0;
    }
    double result = a[0];
    for (int i=1; i<a.length; i++) {
      result = gcd(a[i], result);
      if ((result == 1) || (result == 0))
        return result;
    }
    return result;
  }

  /**
   * Return the gcd (greatest common divisor) of the differences
   * between the elements of double array a.
   **/
  public static double gcd_differences(double[] a) {
    // Euclid's method
    if (a.length < 2) {
      return 0;
    }
    double result = a[1] - a[0];
    for (int i=2; i<a.length; i++) {
      result = gcd(a[i] - a[i-1], result);
      if ((result == 1) || (result == 0))
        return result;
    }
    return result;
  }

  ///
  /// Modulus
  ///

  /** Return z such that (z == x mod y) and (0 <= z < abs(y)). */
  public static final int mod_positive(int x, int y) {
    int result = x % y;
    if (result < 0)
      result += Math.abs(y);
    return result;
  }

  /**
   * Return an array of two integers (r,m) such that each number in NUMS is equal to r (mod m).
   * The largest possible modulus is used, and the trivial constraint that all
   * integers are equal to 0 mod 1 is not returned (null is returned instead).
   * Also, return null if the array is less than 3 elements long.
   **/
  public static int /*@Nullable*/ [] modulus(int[] nums) {
    if (nums.length < 3)
      return null;

    int modulus = Math.abs(gcd_differences(nums));
    if (modulus == 1)
      return null;

    int remainder = nums[0] % modulus;
    if (remainder < 0)
      remainder += modulus;

    return new int[] { remainder, modulus };
  }

  /**
   * The iterator produces Integer values.
   * This can be more efficient than modulus(int[]) if the int[] doesn't already
   * exist, because this does not necessarily examine every value produced by
   * its iterator.
   **/
  public static int /*@Nullable*/ [] modulus_int(Iterator<Integer> itor) {
    if (!itor.hasNext())
      return null;
    int avalue = itor.next().intValue();
    if (!itor.hasNext())
      return null;
    int modulus = Math.abs(avalue - itor.next().intValue());
    if (modulus == 1)
      return null;
    int count = 2;
    while (itor.hasNext()) {
      int i = itor.next().intValue();
      if (i == avalue)
        continue;
      modulus = MathMDE.gcd(modulus, Math.abs(avalue - i));
      count++;
      if (modulus == 1)
        return null;
      }
    if (count < 3)
      return null;
    return new int[] { MathMDE.mod_positive(avalue, modulus), modulus } ;
  }

  /**
   * Return an array of two integers (r,m) such that each number in NUMS is equal to r (mod m).
   * The largest possible modulus is used, and the trivial constraint that all
   * integers are equal to 0 mod 1 is not returned (null is returned instead).
   * <p>
   *
   * This "_strict" version requires its input to be sorted, and no element
   * may be missing.
   * <p>
   *
   * This "_strict" version differs from the regular modulus by requiring
   * that the argument be dense:  that is, every pair of numbers in the
   * argument array is separated by exactly the modulus.
   * <p>
   *
   * The endpoints can be treated in two different ways:  Either exactly
   * like other numbers in the input, or they can merely be checked for the
   * condition without the strict density requirement.
   **/
  public static int /*@Nullable*/ [] modulus_strict(int[] nums, boolean nonstrict_ends) {
    int first_index = 0;
    int last_index = nums.length-1;
    int first_nonstrict = 0; // arbitrary initial value
    int last_nonstrict = 0; // arbitrary initial value
    if (nonstrict_ends) {
      first_nonstrict = nums[first_index];
      first_index++;
      last_nonstrict = nums[last_index];
      last_index--;
    }
    if (last_index - first_index < 2)
      return null;

    int modulus = nums[first_index+1] - nums[first_index];
    if (modulus == 1)
      return null;
    for (int i=first_index+2; i<=last_index; i++)
      if (nums[i] - nums[i-1] != modulus)
        return null;

    int r = mod_positive(nums[first_index], modulus);
    if (nonstrict_ends) {
      if ((r != mod_positive(first_nonstrict, modulus))
          || (r != mod_positive(last_nonstrict, modulus)))
        return null;
    }

    return new int[] { r, modulus };
  }

  /**
   * The iterator produces Integer values.
   * This can be more efficient than modulus(int[]) if the int[] doesn't
   * already exist, because this does not necessarily examine every value
   * produced by its iterator.
   *
   * For documentation, see modulus_strict(int[], boolean).
   * @see #modulus_strict(int[], boolean)
   **/
  public static int /*@Nullable*/ [] modulus_strict_int(Iterator<Integer> itor, boolean nonstrict_ends) {
    if (!itor.hasNext())
      return null;

    int first_nonstrict = 0;    // arbitrary initial value
    int last_nonstrict = 0;     // arbitrary initial value
    if (nonstrict_ends) {
      first_nonstrict = itor.next().intValue();
    }

    int prev = itor.next().intValue();
    if (!itor.hasNext())
      return null;
    int next = itor.next().intValue();
    int modulus = next-prev;
    if (modulus == 1)
      return null;
    int count = 2;
    while (itor.hasNext()) {
      prev = next;
      next = itor.next().intValue();
      if (nonstrict_ends && (! itor.hasNext())) {
        last_nonstrict = next;
        break;
      }

      if (next - prev != modulus)
        return null;
      count++;
    }
    if (count < 3)
      return null;

    int r = MathMDE.mod_positive(next, modulus);
    if (nonstrict_ends) {
      if ((r != mod_positive(first_nonstrict, modulus))
          || (r != mod_positive(last_nonstrict, modulus)))
        return null;
    }

    return new int[] { r, modulus } ;
  }

  /// modulus for long (as opposed to int) values

  /** Return z such that (z == x mod y) and (0 <= z < abs(y)). */
  public static final long mod_positive(long x, long y) {
    long result = x % y;
    if (result < 0)
      result += Math.abs(y);
    return result;
  }

  /**
   * Return an array of two integers (r,m) such that each number in NUMS is equal to r (mod m).
   * The largest possible modulus is used, and the trivial constraint that all
   * integers are equal to 0 mod 1 is not returned (null is returned instead).
   * Also, return null if the array is less than 3 elements long.
   **/
  public static long /*@Nullable*/ [] modulus(long[] nums) {
    if (nums.length < 3)
      return null;

    long modulus = Math.abs(gcd_differences(nums));
    if (modulus == 1)
      return null;

    long remainder = nums[0] % modulus;
    if (remainder < 0)
      remainder += modulus;

    return new long[] { remainder, modulus };
  }

  /**
   * The iterator produces Long values.
   * This can be more efficient than modulus(long[]) if the long[] doesn't already
   * exist, because this does not necessarily examine every value produced by
   * its iterator.
   **/
  public static long /*@Nullable*/ [] modulus_long(Iterator<Long> itor) {
    if (!itor.hasNext())
      return null;
    long avalue = itor.next().longValue();
    if (!itor.hasNext())
      return null;
    long modulus = Math.abs(avalue - itor.next().longValue());
    if (modulus == 1)
      return null;
    int count = 2;
    while (itor.hasNext()) {
      long i = itor.next().longValue();
      if (i == avalue)
        continue;
      modulus = MathMDE.gcd(modulus, Math.abs(avalue - i));
      count++;
      if (modulus == 1)
        return null;
      }
    if (count < 3)
      return null;
    return new long[] { MathMDE.mod_positive(avalue, modulus), modulus } ;
  }

  /**
   * Return an array of two integers (r,m) such that each number in NUMS is equal to r (mod m).
   * The largest possible modulus is used, and the trivial constraint that all
   * integers are equal to 0 mod 1 is not returned (null is returned instead).
   * <p>
   *
   * This "_strict" version requires its input to be sorted, and no element
   * may be missing.
   * <p>
   *
   * This "_strict" version differs from the regular modulus by requiring
   * that the argument be dense:  that is, every pair of numbers in the
   * argument array is separated by exactly the modulus.
   * <p>
   *
   * The endpoints can be treated in two different ways:  Either exactly
   * like other numbers in the input, or they can merely be checked for the
   * condition without the strict density requirement.
   **/
  public static long /*@Nullable*/ [] modulus_strict(long[] nums, boolean nonstrict_ends) {
    int first_index = 0;
    int last_index = nums.length-1;
    long first_nonstrict = 0; // arbitrary initial value
    long last_nonstrict = 0; // arbitrary initial value
    if (nonstrict_ends) {
      first_nonstrict = nums[first_index];
      first_index++;
      last_nonstrict = nums[last_index];
      last_index--;
    }
    if (last_index - first_index < 2)
      return null;

    long modulus = nums[first_index+1] - nums[first_index];
    if (modulus == 1)
      return null;
    for (int i=first_index+2; i<=last_index; i++)
      if (nums[i] - nums[i-1] != modulus)
        return null;

    long r = mod_positive(nums[first_index], modulus);
    if (nonstrict_ends) {
      if ((r != mod_positive(first_nonstrict, modulus))
          || (r != mod_positive(last_nonstrict, modulus)))
        return null;
    }

    return new long[] { r, modulus };
  }

  /**
   * The iterator produces Long values.
   * This can be more efficient than modulus(long[]) if the long[] doesn't
   * already exist, because this does not necessarily examine every value
   * produced by its iterator.
   *
   * For documentation, see modulus_strict(long[], boolean).
   * @see #modulus_strict(int[], boolean)
   **/
  public static long /*@Nullable*/ [] modulus_strict_long(Iterator<Long> itor, boolean nonstrict_ends) {
    if (!itor.hasNext())
      return null;

    long first_nonstrict = 0;    // arbitrary initial value
    long last_nonstrict = 0;     // arbitrary initial value
    if (nonstrict_ends) {
      first_nonstrict = itor.next().longValue();
    }

    long prev = itor.next().longValue();
    if (!itor.hasNext())
      return null;
    long next = itor.next().longValue();
    long modulus = next-prev;
    if (modulus == 1)
      return null;
    int count = 2;
    while (itor.hasNext()) {
      prev = next;
      next = itor.next().longValue();
      if (nonstrict_ends && (! itor.hasNext())) {
        last_nonstrict = next;
        break;
      }

      if (next - prev != modulus)
        return null;
      count++;
    }
    if (count < 3)
      return null;

    long r = MathMDE.mod_positive(next, modulus);
    if (nonstrict_ends) {
      if ((r != mod_positive(first_nonstrict, modulus))
          || (r != mod_positive(last_nonstrict, modulus)))
        return null;
    }

    return new long[] { r, modulus } ;
  }

  ///
  /// Non-Modulus
  ///

  /**
   * Return an array containing all the numbers *not* in its argument array
   * but in the argument's range; that is, bigger than its argument's
   * minimum value and smaller than its argument's maximum value.
   * The result contains no duplicates and is in order.
   **/
  public static int[] missing_numbers(int[] nums) {
    { // avoid modifying parameter
      int[] nums_copy = new int[nums.length];
      System.arraycopy(nums, 0, nums_copy, 0, nums.length);
      nums = nums_copy;
    }
    Arrays.sort(nums);
    int min = nums[0];
    int max = nums[nums.length-1];
    int[] result = new int[max - min + 1 - nums.length];
    int result_index = 0;
    int val = min;
    for (int i=0; i<nums.length; i++) {
      while (val < nums[i]) {
        result[result_index] = val;
        result_index++;
        val++;
      }
      if (val == nums[i]) {
        val++;
      }
    }
    if (result_index == result.length) {
      return result;
    } else {
      // There were duplicates in the nums array, so we didn't fill up
      // the result array.
      int[] new_result = new int[result_index];
      System.arraycopy(result, 0, new_result, 0, result_index);
      return new_result;
    }
  }

  /**
   * This iterator returns all the numbers *not* in its argument array
   * but in the argument's range; that is, bigger than its argument's
   * minimum value and smaller than its argument's maximum value.
   * The result contains no duplicates and is in order.
   * If boolean add_ends is set, then the bracketing endpoints are also
   * returned; otherwise, all returned values are between the minimum and
   * maximum of the original values.
   **/
  static final class MissingNumbersIteratorInt implements Iterator<Integer> {
    int[] nums;
    Iterator<Integer> nums_itor;
    int current_nonmissing;
    int current_missing;
    int current_index;
    boolean add_ends;

    MissingNumbersIteratorInt(int[] nums, boolean add_ends) {
      this.add_ends = add_ends;
      { // avoid modifying parameter
        int[] nums_copy = new int[nums.length];
        System.arraycopy(nums, 0, nums_copy, 0, nums.length);
        nums = nums_copy;
      }
      Arrays.sort(nums);
      current_index = 0;
      current_nonmissing = nums[current_index];
      if (add_ends) {
        current_missing = current_nonmissing - 1;
      } else {
        current_missing = current_nonmissing;
      }
      this.nums = nums;
    }

    // The argument iterator must return the Integers in sorted order
    MissingNumbersIteratorInt(Iterator<Integer> nums_itor, boolean add_ends) {
      this.add_ends = add_ends;
      if (!nums_itor.hasNext())
        throw new Error("No elements in nums_itor");
      current_nonmissing = nums_itor.next().intValue();
      if (add_ends) {
        current_missing = current_nonmissing - 1;
      } else {
        current_missing = current_nonmissing;
      }
      this.nums_itor = nums_itor;
    }

    public boolean hasNext() {
      if (current_missing < current_nonmissing)
        return true;
      // This loop ("while" instead of "if") permits duplicates in nums.
      while (current_missing == current_nonmissing) {
        if (nums != null) {
          current_index++;
          if (current_index >= nums.length) {
            if (add_ends) {
              current_missing++;
              return true;
            } else {
              return false;
            }
          }
          current_nonmissing = nums[current_index];
        } else if (nums_itor != null) {
          if (!nums_itor.hasNext()) {
            if (add_ends) {
              current_missing++;
              return true;
            } else {
              return false;
            }
          }
          // prev_nonmissing is for testing only
          int prev_nonmissing = current_nonmissing;
          current_nonmissing = nums_itor.next().intValue();
          if (! (prev_nonmissing < current_nonmissing))
            throw new Error("Non-sorted Iterator supplied to MissingNumbersIteratorInt: prev_nonmissing = " + prev_nonmissing + ", current_nonmissing = " + current_nonmissing);
        } else {
          throw new Error("Can't happen");
        }
        current_missing++;
        return hasNext();
      }
      if (add_ends) {
        return (current_missing == current_nonmissing + 1);
      } else {
        throw new Error("Can't happen: " + current_missing + " " + current_nonmissing);
      }
    }

    public Integer next() {
      if (!hasNext())
        throw new NoSuchElementException();
      Integer result = new Integer(current_missing);
      current_missing++;
      return result;
    }

    public void remove() {
      throw new UnsupportedOperationException();
    }
  }

  /**
   * Return a tuple of (r,m) where no number in NUMS is equal to r (mod
   * m) but all missing numbers in their range are.  Returns null if the
   * input array has 0 length.
   **/
  public static int /*@Nullable*/ [] nonmodulus_strict(int[] nums) {
    // This implementation is particularly inefficient; find a better way to
    // compute this.  Perhaps obtain the new modulus numbers incrementally
    // instead of all at once.
    if (nums.length == 0)
      return null;
    int range = ArraysMDE.element_range(nums);
    if (range > 65536)
      return null;
    return nonmodulus_strict_int_internal(new MissingNumbersIteratorInt(nums, true));
  }

  private static int /*@Nullable*/ [] nonmodulus_strict_int_internal(Iterator<Integer> missing) {
    // Must not use regular modulus:  that can produce errors, eg
    // nonmodulus_strict({1,2,3,5,6,7,9,11}) => {0,2}.  Thus, use
    // modulus_strict.
    UtilMDE.RemoveFirstAndLastIterator<Integer> missing_nums
      = new UtilMDE.RemoveFirstAndLastIterator<Integer>(missing);
    int[] result = modulus_strict_int(missing_nums, false);
    if (result == null)
      return result;
    if (! check_first_and_last_nonmodulus(result, missing_nums))
      return null;

    return result;
  }

  private static boolean check_first_and_last_nonmodulus(int[] rm, UtilMDE.RemoveFirstAndLastIterator<Integer> rfali) {
    int r = rm[0];
    int m = rm[1];
    int first = rfali.getFirst().intValue();
    int last = rfali.getLast().intValue();
    return ((r != mod_positive(first, m))
            && (r != mod_positive(last, m)));
  }

  /**
   * Return a tuple of (r,m) where no number in NUMS is equal to r (mod
   * m) but all missing numbers in their range are.
   **/
  public static int /*@Nullable*/ [] nonmodulus_strict_int(Iterator<Integer> nums) {
    return nonmodulus_strict_int_internal(new MissingNumbersIteratorInt(nums, true));
  }

  // Old, slightly less efficient implementation that uses the version of
  // missing_numbers that returns an array instead of an Iterator.
  // /**
  //  * Return a tuple of (r,m) where no number in NUMS is equal to r (mod
  //  * m) but all missing numbers in their range are.
  //  */
  // public static int /*@Nullable*/ [] nonmodulus_strict(int[] nums) {
  //   // This implementation is particularly inefficient; find a better way to
  //   // compute this.  Perhaps obtain the new modulus numbers incrementally
  //   // instead of all at once.
  //   if (nums.length == 0)
  //     return null;
  //   int range = ArraysMDE.element_range(nums);
  //   if (range > 65536)
  //     return null;
  //   return modulus(missing_numbers(nums));
  // }

  /**
   * Return a tuple of (r,m) where no number in NUMS is equal to r (mod m)
   * but for every number in NUMS, at least one is equal to every non-r remainder.
   * The modulus is chosen as small as possible, but no greater than half the
   * range of the input numbers (else null is returned).
   **/
  // This seems to give too many false positives (or maybe my probability
  // model was wrong); use nonmodulus_strict instead.
  public static int /*@Nullable*/ [] nonmodulus_nonstrict(int[] nums) {
    if (nums.length < 4)
      return null;
    int max_modulus = Math.min(nums.length/2, ArraysMDE.element_range(nums)/2);

    // System.out.println("nums.length=" + nums.length + ", range=" + ArraysMDE.element_range(nums) + ", max_modulus=" + max_modulus);

    // no real sense checking 2, as common_modulus would have found it, but
    // include it to make this function stand on its own
    for (int m=2; m<=max_modulus; m++) {
      // System.out.println("Trying m=" + m);
      boolean[] has_modulus = new boolean[m]; // initialized to false?
      int num_nonmodulus = m;
      for (int i=0; i<nums.length; i++) {
        int rem = mod_positive(nums[i], m);
        if (!has_modulus[rem]) {
          has_modulus[rem] = true;
          num_nonmodulus--;
          // System.out.println("rem=" + rem + " for " + nums[i] + "; num_nonmodulus=" + num_nonmodulus);
          if (num_nonmodulus == 0)
            // Quit as soon as we see every remainder instead of processing
            // each element of the input list.
            break;
        }
      }
      // System.out.println("For m=" + m + ", num_nonmodulus=" + num_nonmodulus);
      if (num_nonmodulus == 1) {
        return new int[] {ArraysMDE.indexOf(has_modulus, false), m};
      }
    }
    return null;
  }

  /// non-modulus for long (as opposed to int) values

  /**
   * Return an array containing all the numbers *not* in its argument array
   * but in the argument's range; that is, bigger than its argument's
   * minimum value and smaller than its argument's maximum value.
   * The result contains no duplicates and is in order.
   **/
  public static long[] missing_numbers(long[] nums) {
    { // avoid modifying parameter
      long[] nums_copy = new long[nums.length];
      System.arraycopy(nums, 0, nums_copy, 0, nums.length);
      nums = nums_copy;
    }
    Arrays.sort(nums);
    long min = nums[0];
    long max = nums[nums.length-1];
    long[] result = new long[((int) (max - min + 1 - nums.length))];
    int result_index = 0;
    long val = min;
    for (int i=0; i<nums.length; i++) {
      while (val < nums[i]) {
        result[result_index] = val;
        result_index++;
        val++;
      }
      if (val == nums[i]) {
        val++;
      }
    }
    if (result_index == result.length) {
      return result;
    } else {
      // There were duplicates in the nums array, so we didn't fill up
      // the result array.
      long[] new_result = new long[result_index];
      System.arraycopy(result, 0, new_result, 0, result_index);
      return new_result;
    }
  }

  /**
   * This iterator returns all the numbers *not* in its argument array
   * but in the argument's range; that is, bigger than its argument's
   * minimum value and smaller than its argument's maximum value.
   * The result contains no duplicates and is in order.
   * If boolean add_ends is set, then the bracketing endpoints are also
   * returned; otherwise, all returned values are between the minimum and
   * maximum of the original values.
   **/
  static final class MissingNumbersIteratorLong implements Iterator<Long> {
    long[] nums;
    Iterator<Long> nums_itor;
    long current_nonmissing;
    long current_missing;
    int current_index;
    boolean add_ends;

    MissingNumbersIteratorLong(long[] nums, boolean add_ends) {
      this.add_ends = add_ends;
      { // avoid modifying parameter
        long[] nums_copy = new long[nums.length];
        System.arraycopy(nums, 0, nums_copy, 0, nums.length);
        nums = nums_copy;
      }
      Arrays.sort(nums);
      current_index = 0;
      current_nonmissing = nums[current_index];
      if (add_ends) {
        current_missing = current_nonmissing - 1;
      } else {
        current_missing = current_nonmissing;
      }
      this.nums = nums;
    }

    // The argument iterator must return the Integers in sorted order
    MissingNumbersIteratorLong(Iterator<Long> nums_itor, boolean add_ends) {
      this.add_ends = add_ends;
      if (!nums_itor.hasNext())
        throw new Error("No elements in nums_itor");
      current_nonmissing = nums_itor.next().longValue();
      if (add_ends) {
        current_missing = current_nonmissing - 1;
      } else {
        current_missing = current_nonmissing;
      }
      this.nums_itor = nums_itor;
    }

    public boolean hasNext() {
      if (current_missing < current_nonmissing)
        return true;
      // This loop ("while" instead of "if") permits duplicates in nums.
      while (current_missing == current_nonmissing) {
        if (nums != null) {
          current_index++;
          if (current_index >= nums.length) {
            if (add_ends) {
              current_missing++;
              return true;
            } else {
              return false;
            }
          }
          current_nonmissing = nums[current_index];
        } else if (nums_itor != null) {
          if (!nums_itor.hasNext()) {
            if (add_ends) {
              current_missing++;
              return true;
            } else {
              return false;
            }
          }
          // prev_nonmissing is for testing only
          long prev_nonmissing = current_nonmissing;
          current_nonmissing = nums_itor.next().longValue();
          if (! (prev_nonmissing < current_nonmissing))
            throw new Error("Non-sorted Iterator supplied to MissingNumbersIteratorLong: prev_nonmissing = " + prev_nonmissing + ", current_nonmissing = " + current_nonmissing);
        } else {
          throw new Error("Can't happen");
        }
        current_missing++;
        return hasNext();
      }
      if (add_ends) {
        return (current_missing == current_nonmissing + 1);
      } else {
        throw new Error("Can't happen: " + current_missing + " " + current_nonmissing);
      }
    }

    public Long next() {
      if (!hasNext())
        throw new NoSuchElementException();
      Long result = new Long(current_missing);
      current_missing++;
      return result;
    }

    public void remove() {
      throw new UnsupportedOperationException();
    }
  }

  /**
   * Return a tuple of (r,m) where no number in NUMS is equal to r (mod
   * m) but all missing numbers in their range are.  Returns null if the
   * input array has 0 length.
   **/
  public static long /*@Nullable*/ [] nonmodulus_strict(long[] nums) {
    // This implementation is particularly inefficient; find a better way to
    // compute this.  Perhaps obtain the new modulus numbers incrementally
    // instead of all at once.
    if (nums.length == 0)
      return null;
    long range = ArraysMDE.element_range(nums);
    if (range > 65536)
      return null;
    return nonmodulus_strict_long_internal(new MissingNumbersIteratorLong(nums, true));
  }

  private static long /*@Nullable*/ [] nonmodulus_strict_long_internal(Iterator<Long> missing) {
    // Must not use regular modulus:  that can produce errors, eg
    // nonmodulus_strict({1,2,3,5,6,7,9,11}) => {0,2}.  Thus, use
    // modulus_strict.
    UtilMDE.RemoveFirstAndLastIterator<Long> missing_nums
      = new UtilMDE.RemoveFirstAndLastIterator<Long>(missing);
    long[] result = modulus_strict_long(missing_nums, false);
    if (result == null)
      return result;
    if (! check_first_and_last_nonmodulus(result, missing_nums))
      return null;

    return result;
  }

  private static boolean check_first_and_last_nonmodulus(long[] rm, UtilMDE.RemoveFirstAndLastIterator<Long> rfali) {
    long r = rm[0];
    long m = rm[1];
    long first = rfali.getFirst().longValue();
    long last = rfali.getLast().longValue();
    return ((r != mod_positive(first, m))
            && (r != mod_positive(last, m)));
  }

  /**
   * Return a tuple of (r,m) where no number in NUMS is equal to r (mod
   * m) but all missing numbers in their range are.
   **/
  public static long /*@Nullable*/ [] nonmodulus_strict_long(Iterator<Long> nums) {
    return nonmodulus_strict_long_internal(new MissingNumbersIteratorLong(nums, true));
  }

  // Old, slightly less efficient implementation that uses the version of
  // missing_numbers that returns an array instead of an Iterator.
  // /**
  //  * Return a tuple of (r,m) where no number in NUMS is equal to r (mod
  //  * m) but all missing numbers in their range are.
  //  */
  // public static long /*@Nullable*/ [] nonmodulus_strict(long[] nums) {
  //   // This implementation is particularly inefficient; find a better way to
  //   // compute this.  Perhaps obtain the new modulus numbers incrementally
  //   // instead of all at once.
  //   if (nums.length == 0)
  //     return null;
  //   long range = ArraysMDE.element_range(nums);
  //   if (range > 65536)
  //     return null;
  //   return modulus(missing_numbers(nums));
  // }

  /**
   * Return a tuple of (r,m) where no number in NUMS is equal to r (mod m)
   * but for every number in NUMS, at least one is equal to every non-r remainder.
   * The modulus is chosen as small as possible, but no greater than half the
   * range of the input numbers (else null is returned).
   **/
  // This seems to give too many false positives (or maybe my probability
  // model was wrong); use nonmodulus_strict instead.
  public static long /*@Nullable*/ [] nonmodulus_nonstrict(long[] nums) {
    if (nums.length < 4)
      return null;
    int max_modulus = ((int) (Math.min(nums.length/2, ArraysMDE.element_range(nums)/2)));

    // System.out.println("nums.length=" + nums.length + ", range=" + ArraysMDE.element_range(nums) + ", max_modulus=" + max_modulus);

    // no real sense checking 2, as common_modulus would have found it, but
    // include it to make this function stand on its own
    for (int m=2; m<=max_modulus; m++) {
      // System.out.println("Trying m=" + m);
      boolean[] has_modulus = new boolean[m]; // initialized to false?
      int num_nonmodulus = m;
      for (int i=0; i<nums.length; i++) {
        int rem = ((int) (mod_positive(nums[i], m)));
        if (!has_modulus[rem]) {
          has_modulus[rem] = true;
          num_nonmodulus--;
          // System.out.println("rem=" + rem + " for " + nums[i] + "; num_nonmodulus=" + num_nonmodulus);
          if (num_nonmodulus == 0)
            // Quit as soon as we see every remainder instead of processing
            // each element of the input list.
            break;
        }
      }
      // System.out.println("For m=" + m + ", num_nonmodulus=" + num_nonmodulus);
      if (num_nonmodulus == 1) {
        return new long[] {ArraysMDE.indexOf(has_modulus, false), m};
      }
    }
    return null;
  }

}
